The number of shortest paths from point A to | vedclass

Name: Exam Paper Generator | JEE NEET Paper Generator | Vedclass
Brand: Vedclass
Rating: 5 (35 reviews)

Question

(B) To find the number of shortest paths from $A$ to $D$,we observe that all paths must pass through the segment $MN$. Let $S_M$ be the set of paths f

Vedclass · Accepted Answer

$186$

Vedclass · Answer

(B) To find the number of shortest paths from $A$ to $D$,we observe that all paths must pass through the segment $MN$. Let $S_M$ be the set of paths from $A$ to $M$ and $S_N$ be the set of paths from $A$ to $N$. Paths from $A$ to $M$: The grid from $A$ to $M$ is $2$ units wide and $5$ units high. The number of paths is $\frac{(2+5)!}{2!5!} = \frac{7!}{2!5!} = 21$. Paths from $M$ to $D$: The grid from $M$ to $D$ is $2$ units wide and $2$ units high. The number of paths is $\frac{(2+2)!}{2!2!} = \frac{4!}{2!2!} = 6$. Total paths through $M$ = $21 	imes 6 = 126$. Paths from $A$ to $N$: The grid from $A$ to $N$ is $2$ units wide and $4$ units high. The number of paths is $\frac{(2+4)!}{2!4!} = \frac{6!}{2!4!} = 15$. Paths from $N$ to $D$: The grid from $N$ to $D$ is $2$ units wide and $3$ units high. The number of paths is $\frac{(2+3)!}{2!3!} = \frac{5!}{2!3!} = 10$. Total paths through $N$ = $15 	imes 10 = 150$. Since the segment $MN$ is a single vertical step,any path passing through $M$ must pass through $N$ (or vice versa depending on direction). However,the grid structure shows $M$ is above $N$. Thus,any path from $A$ to $D$ must pass through the segment $MN$. The number of paths through $MN$ is the number of paths from $A$ to $N$ multiplied by the number of paths from $M$ to $D$. Paths through $MN = (	ext{Paths } A 	o N) 	imes (	ext{Paths } M 	o D) = 15 	imes 6 = 90$. Using the Principle of Inclusion-Exclusion for paths through $M$ or $N$: Total paths = (Paths through $M$) + (Paths through $N$) - (Paths through both $M$ and $N$) Total paths = $126 + 150 - 90 = 186$.

The number of shortest paths from point $A$ to $D$ (as shown in the figure) is:

Similar Questions

There are $6$ multiple choice questions in an examination. How many sequences of answers are possible,if the first three questions have $4$ choices each and the next three have $5$ choices each?

The number of values of $r$ satisfying $^{69}C_{3r-1} - ^{69}C_{r^2} = ^{69}C_{r^2-1} - ^{69}C_{3r}$ is:

The number of ways to distribute $25$ apples among $4$ boys,such that each boy receives at least $4$ apples,is:

If $a$ denotes the number of permutations of $x + 2$ things taken all at a time,$b$ the number of permutations of $x$ things taken $11$ at a time,and $c$ the number of permutations of $x - 11$ things taken all at a time such that $a = 182bc$,then the value of $x$ is

Each section in the first year of a plus $2$ course has exactly $40$ students. If there are $5$ sections,in how many ways can a set of $4$ student representatives be selected,$1$ from each section?

Vedclass Test Series

Exam Paper Generator

Online Exam Module